package cn.com.mdx.union;

import java.time.Duration;
import java.time.LocalDateTime;
import java.util.Random;

/**
 * @author huangyuan
 * @date 2020/5/28
 * @description 联合查找
 */
public class UF {

    private final int[] rank; //节点等级
    private final int[] parent; //父节点
    private int count; //数的个数

    public UF(int n) {
        if (n <= 0) throw new IllegalArgumentException("传递参数不合法，请传递大于0的数");
        count = n;
        rank = new int[n];
        parent = new int[n];
        //初始化
        for (int i = 0; i < n; i++) {
            rank[i] = 1;
            parent[i] = i;
        }
    }

    /**
     * @param p 节点p
     * @return 节点p的根节点
     * @description 获取节点p的根节点
     * @date 2020/6/12 2:59 下午
     */
    public int find(int p) {
        validate(p);
        while (p != parent[p]) {
            //路径进行减半压缩
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    /**
     * @param p 节点p
     * @param q 节点q
     * @description 将节点p和q连接起来
     * @date 2020/6/12 2:29 下午
     */
    public void union(int p, int q) {
        //获取根节点
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;
        //连接树：将高度小的树连接到高度大的树上
        if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
        else if (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
        else {
            //如果树的高度相同，则进行默认连接：q连接到p上，q所在的树高度加1
            parent[rootQ] = rootP;
            rank[rootP]++;
        }
        count--;
    }

    /**
     * @param p 节点p
     * @param q 节点q
     * @return true 表示连接 false 表示未连接
     * @description 节点p和q是否连接
     * @date 2020/6/12 3:34 下午
     */
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    /**
     * @param p 节点p
     * @description 校验节点是否合法
     * @date 2020/6/12 2:42 下午
     */
    private void validate(int p) {
        int n = parent.length;
        if (p > n || p < 0) throw new IllegalArgumentException("索引值应在0" + "和" + (n - 1) + "之间");
    }

    public static void main(String[] args) {
        randomTest();
        UnionTest();
    }

    private static void randomTest() {
        UF uf = new UF(10000000);
        LocalDateTime runBefore = LocalDateTime.now();
        Random random = new Random();
        int randomNum = uf.parent.length;
        for (int i = 0; i < randomNum; i++) {
            uf.union(random.nextInt(randomNum), random.nextInt(randomNum));
        }
        System.out.println(uf.connected(random.nextInt(randomNum), random.nextInt(randomNum)));
        System.out.println("树的数量为：" + uf.count);
        LocalDateTime runAfter = LocalDateTime.now();
        System.out.println("运行时间为：" + Duration.between(runBefore, runAfter).toMillis());
    }

    public static void UnionTest() {
        UF uf = new UF(100);
        uf.union(5, 6);
        uf.union(7, 9);
        uf.union(4, 98);
        uf.union(97, 2);
        uf.union(2, 9);
        uf.union(9, 73);
        uf.union(73, 4);
        uf.union(4, 5);
        System.out.println(uf.connected(5, 99));
        System.out.println(uf.connected(5, 98));
        System.out.println(uf.connected(4, 73));
        System.out.println(uf.connected(2, 6));
    }

}
